import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode :  42. 接雨水
 * @author: WXY
 * @create: 2023-02-03 17:00
 * @Version 1.0
 **/
public class Num042_trap {
    //双指针方式
    public static int trap_1(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) continue;
            int rHeight = height[i];
            int lHeight = height[i];
            for (int r = i + 1; r < height.length; r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i - 1; l >= 0; l--) {
                if (height[l] > lHeight) lHeight = height[l];
            }
            int minHeight = Math.min(rHeight, lHeight);
            int cueHeight = minHeight - height[i];
            if (cueHeight > 0) sum += cueHeight * 1;
        }
        return sum;
    }


    public static int trap_2(int[] height) {
        int sum = 0;
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];
        int size = maxRight.length;
        maxLeft[0] = height[0];
        for (int i = 1; i < size; i++) {
            maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
        }
        maxRight[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);
        }
        for (int i = 0; i < size; i++) {
            int curHeight = Math.min(maxLeft[i], maxRight[i]) - height[i];
            sum += curHeight * 1;
        }
        return sum;
    }

    public static int trap(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int curIndex = stack.pop();
                if (!stack.isEmpty()) {
                    int leftHeight = stack.peek();
                    int minRecordHeight = Math.min(height[leftHeight], height[i]) - height[curIndex];
                    int weight = i - stack.peek() - 1;
                    sum += minRecordHeight * weight;
                }
            }
            stack.push(i);

        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int sum = trap(arr);
        System.out.println(sum);
    }
}
